/*
题目: 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
https://leetcode.cn/problems/set-matrix-zeroes/
 */
public class SetZeroes {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[m];
        List<int[]> place = new ArrayList<> ();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    place.add(new int[] {i, j});
                }
            }
        }

        while (!place.isEmpty()) {
            int[] cur = place.remove(place.size() - 1);
            int i = cur[0];
            int j = cur[1];
            if (!row[i]) {
                modifyRow(matrix[i], m);
                row[i] = true;
            }
            if (!col[j]) {
                modifyCol(matrix, n, j);
                col[j] = true;
            }
        }
    }

    private void modifyRow(int[] nums, int m) {
        for (int i = 0; i < m; i++) {
            nums[i] = 0;
        }
    }

    private void modifyCol(int[][] nums, int n, int m) {
        for (int i = 0; i < n; i++) {
            nums[i][m] = 0;
        }
    }
}
